package offer;

import java.util.*;

@FunctionalInterface
public interface PushDominoes {
    String pushDominoes(String dominoes);
}

class PushDominoesImpl1 implements PushDominoes{
    static final String TEST_01 = "RR.L";

    public static void main(String[] args) {
        new PushDominoesImpl1().pushDominoes(TEST_01);
    }

    /**
     * 写不出来
     * @param dominoes
     * @return
     */
    @Override
    @Deprecated
    public String pushDominoes(String dominoes) {
        // 平凡情况
        if(dominoes.length() == 1){
            return dominoes;
        }else if(dominoes.length() == 2){
            char s1 = dominoes.charAt(0), s2 = dominoes.charAt(1);
            if(s1 == '.'){
                if(s2 == 'L'){
                    return "LL";
                }else{
                    return s1 + "" + s2;
                }
            }else if(s1 == 'L'){
                return dominoes;
            }else if(s1 == 'R'){
                if(s2 == 'L'){
                    return "..";
                }else{
                    return "RR";
                }
            }
        }
        StringBuilder ans = new StringBuilder();
        Queue<Character> queue = new LinkedList<>();
        int n = dominoes.length();
        int cur = 0;
        while (cur < n){
            char curChar = dominoes.charAt(cur);
            cur++;
            if(queue.isEmpty()){
                if(curChar == 'L'){
                    ans.append('L');
                }else{
                    queue.offer(curChar);
                }
            }else if(queue.size() == 1){
                if(curChar == '.'){
                    queue.offer('.');
                }else if(curChar == 'L'){
                    ans.append('R');
                    ans.append('L');
                    queue.poll();
                }else if(curChar == 'R'){
                    ans.append('R');
                }
            }else if(queue.size() == 2) {
                if(curChar == 'R'){
                    ans.append('R');
                    ans.append('R');
                }else if(curChar == 'L'){
                    ans.append('R');
                    ans.append('.');
                    ans.append('L');
                }else if(curChar == '.')
                queue.poll();
                queue.poll();
            }
        }
        if(!queue.isEmpty()){
            if(queue.size() == 1){
                // 'R'
                ans.append('R');
            }else if(queue.size() == 2){
                // R.
                ans.append('R');
                ans.append('R');
            }
        }
        return ans.toString();
    }
}

class PushDominoesImpl2 implements PushDominoes{
    /**
     * 抄一遍题解，不会写
     * @param dominoes
     * @return
     */
    @Override
    public String pushDominoes(String dominoes) {
        int n = dominoes.length();
        Deque<Integer> deque = new ArrayDeque<>();
        int[] time = new int[n];
        Arrays.fill(time, -1);
        List<Character>[] force = new List[n];
        for (int i = 0; i < n; i++) {
            force[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            char f = dominoes.charAt(i);
            if(f != '.'){
                deque.offer(i);
                time[i] = 0;
                force[i].add(f);
            }
        }

        char[] res = new char[n];
        Arrays.fill(res, '.');
        while(!deque.isEmpty()){
            int i = deque.poll();
            if(force[i].size() == 1){
                char f = force[i].get(0);
                res[i] = f;
                int ni = f == 'L' ? i - 1 : i + 1;
                if(ni >= 0 && ni < n){
                    int t = time[i];
                    if(time[ni] == -1){
                        deque.offer(ni);
                        time[ni] = t + 1;
                        force[ni].add(f);
                    }else if(time[ni] == t + 1){
                        force[ni].add(f);
                    }
                }
            }
        }

        return new String(res);
    }
}
class pushDominoesImpl3 implements PushDominoes{

    @Override
    public String pushDominoes(String dominoes) {
        char[] s = dominoes.toCharArray();
        int n = s.length, i = 0;
        char left = 'L';
        while(i < n){
            int j = i;
            while(j < n && s[j] == 'i'){
                j++;
            }
            char right = j < n ? s[j] : 'R';
            if(left == right){
                while(i < j){
                    s[i++] = right;
                }
            }else if(left == 'R' && right == 'L'){
                int k = j - 1;
                while(i < k){
                    s[i++] = 'R';
                    s[k--] = 'L';
                }
            }
            left = right;
            i = j + 1;
        }

        return new String(s);
    }
}